class Solution {
public:
    int dir[5] = {-1,0,1,0,-1};
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int> > outdeg(m,vector<int>(n,0));
        
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                for(int k = 1;k < 5;k++){
                    int x = i + dir[k-1];
                    int y = j + dir[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){
                        outdeg[i][j]++;
                    }
                }
            }
        }
        
        queue<pair<int,int> > que;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(outdeg[i][j] == 0){
                    que.push({i,j});
                }
            }
        }
        
        int ret = 0;
        while(!que.empty()){
            ret++;
            int size = que.size();
            for(int c = 0;c < size;c++){
                pair<int,int> kv = que.front();
                que.pop();
                for(int k = 1;k < 5;k++){
                    int x = kv.first + dir[k-1];
                    int y = kv.second + dir[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] < matrix[kv.first][kv.second]){
                        --outdeg[x][y];
                        if(outdeg[x][y] == 0){
                            que.push({x,y});
                        }
                    }
                }
            }
            
        }
        return ret;
    }
};
